The packet scheduling algorithm in a wireless multihop network is usually central-unit processing-based. This type of algorithm, although effective, is costly in terms of computing complexity and not scalable with the network size and the traffic demand. This type of algorithm requires sending every possible combination of transmission and receiving and the corresponding signal-to-noise-ratio (SNR) to the base station (BS), and uses a brutal force method to find the optimal combination. In an actual system, it is difficult to estimate the SNR, not to mention the SNR for all the combinations. Besides, the SNR estimation is only the beginning. The real computation is in the central-unit processing-based packet scheduling.
In a multi-hop wireless network, a relay is for storing and forwarding the packets received at BS to the network node of the mobile station (MS), and vice versa. In other words, the MS in a multi-hop wireless network can also transmit packets from a BS to a relay, and packets from a relay to an MS.
A relay network is a network that has relays between the BS and the MS. There are several advantages of a relay network. The distance of the transmit-receive pair is shorter, and the required transmission power can be reduced in order to expand the service coverage area. The network throughput is therefore increased because the BS, MS, and relay are allowed to transmit packets simultaneously. The channel reuse is also possible by spatial multiplexing technique.
FIG. 1A shows a schematic view of a conventional single cell multihop wireless network. The wireless network includes a base station BS, two relays R1, R2, and four users (mobile station) M1-M4. FIG. 1B shows a schematic view of a conventional multiple-cells multi-hop wireless network. The wireless network includes three base stations BS1-BS3, four relays R1-R4, and eight users M1-M8. In FIGS. 1A & 1B, the variable vj on each network link indicates whether the network link is currently transmitting.
However, if the packets for transmission are not appropriately scheduled, each advantage of using a relay is also accompanied by side effects. For example, when the service coverage area is expanded, the packets from MS are moving among several relays before they reach their destination. Therefore, if the relays do not schedule the packet transmission carefully, the wireless network resources may be wasted. On the other hand, as the simultaneous packet transmission is allowed in a multihop wireless network, the frequent data packet collision may occur. In this case, the performance will greatly decrease.
A good packet scheduling technique not only requires the avoidance of packet collision, but also exploits the spatial reuse characteristics of the multihop wireless network in order to maximize the system throughput. As shown in FIG. 1A, if the outcome of the packet scheduling algorithm is {v1, v2, v3, . . . , v10}={0,1,0,0,1,0,0,0,0,1}, instead of {0,1,0,0,0,0,0,0,0,0}, where vj=1 indicates the network link is currently transmitting, and vj=0 indicates that the network link is not transmitting, the network overall performance is better. This is because the first schedule includes three network links transmitting, while the second schedule only has one link transmitting. It is also worth noticing that the schedule {0,1,0,0,0,0,0,1,1,0} is not an effective schedule as the three packets transmitting to the user M3 will collide.